package JZ.JZ66;

/**
 * @author corn
 * @create 2020-07-17-21:05
 */
public class MovingCountJZ66 {

}

/**
 *
 * 首先在某个节点处，要调用递归来决定某个位置的下一步去哪，此时有4个选择，每个选择都会进入下一个递归调用。
 * 当进入某个位置时，应当标记这个位置已访问过，避免之后又来到这里，从而重复计算，
 * 因此设计一个boolean的数组，这里设计的二维，也可以通过压缩，使用一维数组来表征某个位置是否访问。
 * 二维就是记录横纵坐标即第i行第j列的数据被访问了，直观，推荐新手用二维。接着就是边界条件和递归结束的条件的判断了。
 *   这类型题也是有套路的，主方法在原点作为起点，调用第一次递归后，在递归方法中，
 * 首先判断边界条件以及题目中所提的要求是否满足（本题的要求就是cal方法中的实现），
 * 都没问题，说明该位置可以访问，然后改变对应位置的标记。然后就是以该节点为中心，
 * 考虑下一步怎么走，本题就是4种走法，可以分开写，也可以一起写，由于本题是计数，
 * 所以就直接加在一起。然后return这些求和结果再+1，求和结果是下一步走的结果，而+1是本次访问此时的节点的次数。
 */
class Solution8 {

    public int movingCount(int threshold, int rows, int cols) {
        if (rows <= 0 || cols <= 0 || threshold < 0)
            return 0;

        boolean[][] isVisited = new boolean[rows][cols];//标记，判断该点是否已经确认为可抵达
        //开始移动，（0，0）为起始点
        int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);
        return count;
    }

    private int movingCountCore(int threshold,int rows,int cols,int row,int col, boolean[][] isVisited) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row][col] || //判断到点是否越界或者已经被访问过
                cal(row) + cal(col) > threshold )//判断该点是否超过了限制数值
            return 0;
        //经过以上限制条件判断后，可以判定该点可以抵达并没有抵达过。
        isVisited[row][col] = true;
        return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row + 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row, col - 1, isVisited)
                + movingCountCore(threshold, rows, cols, row, col + 1, isVisited);
    }

    private int cal(int num) {
        int sum = 0;
        //先得个位数，再得十位数
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
